//#define  _CRT_SECURE_NO_WARNINGS
//
//class Solution {
//public:
//    int fib(int n) {
//        return dfs(n);
//    }
//    int memo[31];
//    int dfs(int n)
//    {
//        if (memo[n]) return memo[n];
//        if (n == 1 || n == 0) return n;
//
//        memo[n] = dfs(n - 1) + dfs(n - 2);
//        return memo[n];
//    }
//};